1541. Series of Powers

In this problem you must find the sum of powers:

S(l, h, k) = l^k + (l + 1)^k + (l + 2)^k + … + (h – 1)^k + h^k

Given the values of l, h and k your job is to find the value of S(l, h, k).

Input. Consists of no more than 9999 test cases. Each line contains three integers l, h (0 £ l £ h £ 15000000, |l – h| £ 1000) and k (1 ≤ k ≤ 15000000). Input is terminated by a line with three -1.

Output. For each test case print in a separate line its serial number in four fields and the approximate value of S(l, h, k). This approximate value should be of the form 0.ddddddedddddddddd. The value of mantissa is always less than 1 and has six digits after the decimal point. If mantissa is not zero, the first digit after the decimal point must not be zero. If value of the exponent is irrelevant (does not effect the value of the number) set its value as 1. Follow the exact formatting shown in the sample output.

Sample input	Sample output
1 10 10 10 15 100 -1 -1 -1	Case 0001: 0.149143e0000000011 Case 0002: 0.406971e0000000118

SOLUTION

mathematics

Algorithm analysis

Represent each term i^k in the form . For example, the exponent of the number h^k = equals to klgh. Since |l – h| £ 1000, then the exponent of other degrees will not differ much from klgh. Let exponent = . Therefore, instead of adding the terms i^k we shall sum up = = . During such summation the mantissa value will not be too large, so for its calculation its sufficient to use double type. Separately handle the case when the desired amount equals to zero. Then the mantissa must be set to zero, and the exponent to 1.

Example

Consider the second test, where it is necessary to calculate the sum

10¹⁰⁰ + 11¹⁰⁰ + … + 15¹⁰⁰

The exponent of the number 10¹⁰⁰ equals to 100, the exponent of the number 15¹⁰⁰ = 10^100lg15 equals to 100lg15 ≈ 117,609. Let exponent = 117. Divide the required sum by 10¹¹⁷ and calculate it in a variable of double type:

(10¹⁰⁰ + 11¹⁰⁰ + … + 15¹⁰⁰ ) / 10¹¹⁷ = (10¹⁰⁰ + 10^100lg11 + … + 10^100lg15 ) / 10¹¹⁷ =

10^-17 + 10^-12,861 + … + 10^0,609 ≈ 4,06971

As the received sum is not less than 1, divide it by 10. The obtained mantissa equals to 0,406971. The exponent will be increased by one, and becomes 118.

Algorithm realization

Read the input data.

while(scanf("%d %d %d",&l,&h,&k),l + h + k > 0)

{

Zero out the current value of the mantissa s. In an integer variable exponent evaluate the integer part of the exponent of a number h^k = .

s = 0; exponent = k * log10(1.0*h);

Add the value of to the mantissa s for each i from l to h.

for(i = l; i <= h; i++)

s += pow(10,k*log10(1.0*i) - exponent);

If the mantissa is not less than one, then do it that way.

while (s >= 1) s /= 10, exponent++;

The exceptional case can arise when the result of the sum equals to 0. Then mantissa equals to zero and the value of the exponent is not essential. Set s = 0, exponent = 1

if (!h) s = 0, exponent = 1;

printf("Case %04d: %.6lfe%010d\n", cs++, s, exponent);

}

Java realization

import java.util.*;

import java.io.*;

public class Main

{

public static void main(String[] args)

throws Exception

{

PrintWriter out = new PrintWriter(System.out,true);

BufferedReader in =

new BufferedReader(new InputStreamReader(System.in));

String stroka;

int cs = 1;

while(!(stroka = in.readLine()).equals("-1 -1 -1"))

{

StringTokenizer st = new StringTokenizer(stroka);

int l = Integer.parseInt(st.nextToken());

int h = Integer.parseInt(st.nextToken());

int k = Integer.parseInt(st.nextToken());

double s = 0;

int exponent = (int) (k * Math.log10(h));

for(int i = l; i <= h; i++)

s += Math.pow(10,k * Math.log10(i) - exponent);

while (s >= 1) { s /= 10; exponent++; }

if (h == 0) { s = 0; exponent = 1;}

out.printf(Locale.US,"Case %04d: %.6fe%010d\n",

cs++, s, exponent);

}

}

}